package com.LeeCode;

/**
 * 重新排序得到 2 的幂
 */

public class Code869 {
    public static void main(String[] args) {
        int n = 61;
        System.out.println(new Code869().reorderedPowerOf2(n));
    }

    public boolean reorderedPowerOf2(int n) {
        int[] cnt = new int[10];
        int count = 0;
        while (n > 0) {
            int digit = n % 10;
            cnt[digit]++;
            n /= 10;
            count++;
        }
        for (int i = 1; i < 10; i++) {
            if (cnt[i] == 0) continue;
            cnt[i]--;
            if (dfs(i, 1, cnt, count)) return true;
            cnt[i]++;
        }
        return false;
    }

    private boolean dfs(int num, int index, int[] cnt, int count) {
        if (index == count) return (num & (num - 1)) == 0;

        for (int i = 0; i < 10; i++) {
            if (cnt[i] == 0) continue;
            cnt[i]--;
            if (dfs(num * 10 + i, index + 1, cnt, count)) return true;
            cnt[i]++;
        }
        return false;
    }
}
